#include <iostream>
#include <vector>
using namespace std;

template <typename T>
void printVector(vector<T> v)
{
	for(auto bg = v.begin() ; bg != v.end(); ++bg)
		cout<<*bg<<',';
	cout<<endl;
}

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
    	if(input.empty() || k <= 0 || k > input.size())
    		return vector<int>(0);
    	else if(k == input.size())
    		return input;
        return quickSortCore(input,0,input.size()-1,k);
    }
    int medium(vector<int> &v,int bg,int ed)
    {
    	int md = (bg+ed)/2;
    	if(v[bg] > v[md])
    		swap(v[bg],v[md]);
    	if(v[bg] > v[ed])
    		swap(v[bg],v[ed]);
    	if(v[md] > v[ed])
    		swap(v[md],v[ed]);

    	swap(v[md],v[ed-1]);
    	return v[ed-1];
    }
    vector<int> quickSortCore(vector<int> &v,int start,int end,int k)
    {
    	int comp = medium(v,start,end);
    	int i = start,j = end -1;
    	while(true)
    	{
    		while(comp > v[++i] );
    		while(comp < v[--j]);
    		if(i < j)
    			swap(v[i],v[j]);
    		else
    			break;
    	}
    	swap(v[i], v[end-1]);
    	if(i < k && i+1 < end)
    		return quickSortCore(v,i+1,end,k);
    	else if(i > k && start < i-1)
    		return quickSortCore(v,start,i-1,k);
		return vector<int>(v.begin(),v.begin() + k);
    }

    void swap(int &a,int &b)
    {
    	int temp = a;
    	a = b;
    	b = temp;
    }


};


int main()
{
	Solution s;
	vector<int> v{4,5,1,6,2,7,3,8};
	vector<int> result = s.GetLeastNumbers_Solution(v,4);
	printVector(result);
	return 0;
}